Digital systems transmit a stream of information which is represented by string of bits of 1's and 0's. A group of bits forms a byte and groups of bytes form records. As one digital system communicates with another system, a sequence of records are sent over some form of communication link or channel. The channel may be a disk read-head, or the wires between two telephones, or even the air waves over which satellites communicate with ground based antenna dishes linked to signal receiving equipment.
One way in the art for increasing the reliability of data transmitted through communication channels is by using code constrained sequences. An example of code is the run-length-limited code, used exclusively in magnetic or optical recording, wherein each 1 in a coded bit sequence is separated from an adjacent 1 by a stream of 0's at least equal to a minimum quantity d but not exceeding a maximum number k. Two of the most common (d,k) codes to constrain such sequences are the (1,7) and (2,7) codes.
Another example of code commonly used sod in communications is the parity check, in which a bit is added to a byte to make the sum of all ones in the byte odd. Any error making the sum of all ones even is detected by this code.
A single error occurs when a binary symbol is changed to another binary symbol, i.e., either a 0 gets transformed into a 1 (denoted 0 1) or a 1 becomes a 0 (denoted 1 0). Double adjacent errors occur in a (d,k) code when a (0 1) (1 0) or (1 0) (0 1). An error affecting more than two bits in the sequence but remaining localized is defined as a burst error. All the above errors involve the modification of binary symbols. Bit synchronization errors occur when binary symbols are inserted or deleted.
Synchronization is a method wherein known sequences of 1's and 0's, or codewords, are injected into the bit stream at regular intervals. The receiver checks for the position of these markers. If the marker is at its expected position within the stream then the data bits transmitted up to that point are at least synchronous. In other words, the number of bits transmitted between markers equals the number of bits received between markers. A loss of synchronization is determined by a change in the location of the markers. If the sync marker is not at its location then symbol deletions or additions have occurred between the markers. This occurrence is known as a bit synchronization loss.
The following example illustrates the catastrophic nature of a loss of bit synchronization.
Assume that the following information string A of length 100 bits has been transmitted. ##STR1## Encoding string A into a (1,7)-constrained sequence of length 150 produces string B. Notice that in the (1,7) code used to generate string B, at most a single 1 will be followed by at most 7 consecutive 0's. ##STR2## Now, assume that string C was received. ##STR3## Observe that at bit 39 of string B (indicated by parenthesis), a single 0 has been deleted thereby causing a loss of synchronization wherein all subsequent bits shift one bit to the left. The `*` in string C indicates where the deletion occurred on the received string.
If the result of decoding string C is EXCLUSIVE-OR'd with the original string A to determine the degree of the error introduced, the following error string R is obtained. Note that a 0 denotes no error for that particular bit in the original transmitted sequence. ##STR4## Observe that starting at bit 24, (indicated by parenthesis), a continuous string of errors has resulted from the single deletion of one bit. In this example, the receiver would be out of synchronization with the transmitter from bit 39 onward and, absent any re-synchronization detection and recovery, the data would be lost.
Although deletions and insertions are not as common as other kinds of errors, it is important to this art to be able to detect synchronization errors and distinguish them from random and peak shift errors because if the correct number of insertions or deletions that occurred can be correctly determined in a transmitted interval of data the overall damage to the information stream may be repairable or at least minimized by the subsequent restoration of synchronization. It is even more important to this art to be able to recover from these errors, specifically in the widely used code-constrained sequences.